package club.vann.nowcoder;

import java.util.Locale;

/**
 * <p>难度：Medium</p>
 * <p>题目：最常回文子串</p>
 * <p>描述：对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
 *
 * 给定字符串A以及它的长度n，请返回最长回文子串的长度。
 *
 * 示例1
 * 输入
 * 复制
 * "abc1234321ab",12
 * 返回值
 * 复制
 * 7</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-04-15:08:43:05
 */
public class NC17 {
    public static void main(String[] args) {
        NC17 nc17 = new NC17();
        System.out.println("Result["+TestCase.ANS+"] : " + nc17.getLongestPalindrome(TestCase.A, TestCase.N));
    }

    /**
     * 解法一：
     *
     * @param A
     * @param n
     * @return
     */
    public int getLongestPalindrome(String A, int n) {
        // write code here
        if(n == 0) {
            return 0;
        }
        int max = 0;
        char[] ch = A.toCharArray();

        boolean[][] dp = new boolean[n][n];

        for(int right = 0; right < n; right ++) {
            for(int left = 0; left <= right; left ++) {
                if(ch[left] == ch[right]) {
                    if(left == right) {
                        dp[left][right] = true;
                    } else if(right-left+1 == 2){
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left+1][right-1];
                    }

                } else {
                    dp[left][right] = false;
                }

                if(dp[left][right]) {
                    max = Math.max(max, right-left+1);
                }
            }
        }
        return max;
    }

    static class TestCase {
        public static int ANS = 7;
        public static String A = "abc1234321ab";
        public static int N = 12;
    }
}
